package com.zj.leetcode.medium.greed;

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: algorithm
 * @description: 无重叠区间
 * 435 non-overlapping-intervals
 * @author: Zhang Bo
 * @create: 2022-03-27 23:06:43
 **/
public class NonOverlappingIntervals {
    public static void main(String[] args) {
        int[][] intervals = {{1,2},{1,5},{2,3},{3,4},{5,6},{6,7},{7,8}};
        Solution solution = new NonOverlappingIntervals().new Solution();
        solution.eraseOverlapIntervals(intervals);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int eraseOverlapIntervals(int[][] intervals) {

            if (intervals.length == 0) {
                return 0;
            }


            List<int[]> list =
                    Arrays.stream(intervals)
                            .sorted((a, b) -> {
                                return a[1] - b[1];
                            })
                            .collect(Collectors.toList());

            int s = list.size();
            int right = list.get(0)[1];
            int ans = 1;
            for (int i = 1; i < s; ++i) {
                if (list.get(i)[0] >= right) {
                    ++ans;
                    right = list.get(i)[1];
                }
            }
            return s - ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
